<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>fenwick tree 树状数组</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="fenwick-tree-树状数组">fenwick tree 树状数组</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=CWDQJGaN1gY&amp;list=PLrmLmBdmIlpv_jNDXtJGYTPNQ2L1gdHxu&amp;index=24">https://www.youtube.com/watch?v=CWDQJGaN1gY&amp;list=PLrmLmBdmIlpv_jNDXtJGYTPNQ2L1gdHxu&amp;index=24</a></li>
<li><a href="https://www.luogu.com.cn/blog/Chanis/super-BIT">https://www.luogu.com.cn/blog/Chanis/super-BIT</a></li>
<li><a href="https://www.cnblogs.com/xenny/p/9739600.html">https://www.cnblogs.com/xenny/p/9739600.html</a></li>
<li>复杂的可能还有二维的树状数组</li>
</ul>
<p>和线段树比较</p>
<ul>
<li>比线段树更好实现？</li>
<li>最坏情况下比线段树更好</li>
<li>构建O(n)</li>
<li>更新，查询O(lgn)</li>
</ul>
<p><img src="file:///e:\gitee\leetcode\segmenttree\pics\fenwick1.png" alt="fenwick1.png"></p>
<h1 id="1-单点更新范围查询">1.  单点更新，范围查询</h1>
<p>D:\myproject\python\leetcode\tree\<a href="http://fenwicktree1.py">fenwicktree1.py</a></p>
<pre><code><code><div># coding:utf-8
#
# fenwick tree
#
# https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/FenwickTree.java
#

import click
import pysnooperp


def lowbit(x):
    return x &amp; (-x)

class Fenwick(object):

    def __init__(self, nums):
        self.nums = nums
        self.n = len(nums)
        self.c = [0] * (self.n+1)  # 这里很关键， 创建的数组c[]大小是n+1， 不是n

        for i in range(1, self.n+1):  # 从1开始遍历，从0开始的话，会死循环。
            self.update(i, nums[i-1])

    def update(self, i, k):
        while i &lt;= self.n:
            self.c[i] += k
            i = i + lowbit(i)


    def sum(self, i):
        ans = 0
        while i &gt; 0:
            ans += self.c[i]
            i = i - lowbit(i)
        return ans

@click.group()
def main():
    pass

@main.command()
def test1():
    nums = [3,9,-1, 2, 7, 0, 1, 10]
    f = Fenwick(nums)
    for i in range(len(nums)):
        ans = f.sum(i)
        print(f&quot;{i} {ans}&quot;)

if __name__ == '__main__':
    main()

</div></code></code></pre>

    </body>
    </html>